package two.chapter_2.c2_1;

/**
 * 选择排序：第一次挑选出最小的元素和第一个元素交换位置，
 *          第二次挑选剩余元素中最小的元素和第二个元素交换位置，
 *          直到最后一个元素
 * @param <Item>
 */
public class SelectionSort<Item extends Comparable<Item>>  extends Sortable<Item> {

    /**
     * 最坏的情况 比较次数  N-1+N-2+...+1=N(N-1)/2
     *           交换次数 N
     * 最好的情况 比较次数  N-1+N-2+...+1=N(N-1)/2
     *           交换次数 N
     *
     * 所以平均情况  比较次数为N(N-1)/2
     *             交换次数为N
     * @param items
     */
    @Override
    public void sort(Item[] items) {
        for (int i=0;i<items.length;i++){
            int minIndex =i; //N次
            for (int j=i+1;j<items.length;j++){//
                if (less(items[j],items[minIndex])){
                    minIndex=j;
                }
            }
            //if (i!=minIndex)
            exch(i,minIndex,items);
        }
    }
}
